Fast Spherical Centroidal Voronoi Mesh Generation: A Lloyd-preconditioned LBFGS Method in Parallel

摘要

Centroidal Voronoi tessellation (CVT)-based mesh generation is a veryeffective technique for creating high-quality Voronoi meshes and their dualDelaunay triangulations that often play a crucial role in applications,including ocean and atmospheric simulations using finite volume schemes. In thenext generation climate models, the spacing scales change dramatically acrossthe whole sphere and require ultra-high resolution and smooth transitions fromcoarse to fine grid regions. Thus fast and robust spherical CVT (SCVT) meshingalgorithms become highly desirable. In this paper, we first propose aLloyd-preconditioned limited-memory BFGS method for constructing SCVTs that isalso applicable to the construction of CVTs of general domains. This method isthen parallelized based on overlapping domain decomposition, enabling excellentscalability on distributed systems. Results of several computationalexperiments show that the new method could incur computational time costs oneorder of magnitude smaller compared with some existing methods for generatinglarge-scale highly variable-resolution meshes, while also providingsignificantly improvements in mesh quality.